212E - IT Restaurants - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define endl "\n"

const int N=5e3+100;
bitset<5005> ans;
int sz[N],head[N],ver[2*N],Next[2*N];
int tot,n;

void add(int x,int y)
{
	ver[++tot]=y; Next[tot]=head[x]; head[x]=tot;
	ver[++tot]=x; Next[tot]=head[y]; head[y]=tot;
}

void dfs(int x,int fa)
{
	sz[x]=1;
	int sums=0;
	bitset<5005> dp;
	dp[0]=1;
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i];
		if(y==fa) continue;
		dfs(y,x);
		sums+=sz[y];
		for(int j=n;j>=sz[y];j--){
			if(dp[j-sz[y]]) dp[j]=1;
		}
	}
	if(sums==0) return;
	int now=n-1-sums;
	for(int j=n;j>=now;j--){
		if(dp[j-now]) dp[j]=1;
	}
	ans|=dp;
	sz[x]+=sums;
}

void solve()
{
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	dfs(1,0);
	int tot=0;
	for(int i=1;i<n-1;i++) if(ans[i]) tot++;
	cout<<tot<<endl;
	for(int i=1;i<n-1;i++){
		if(ans[i]) cout<<i<<" "<<(n-1-i)<<endl;
	}
}

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t;
	// cin>>t;
	t=1;
	while(t--){
		solve();
	}
	return 0;
}